package leetcode;

/**
 * 148.排序链表
 * 在 O(n log n) 时间复杂度和常数级空间复杂度下，对链表进行排序。
 * <p>
 * 示例 1:
 * <p>
 * 输入: 4->2->1->3
 * 输出: 1->2->3->4
 * 示例 2:
 * <p>
 * 输入: -1->5->3->4->0
 * 输出: -1->0->3->4->5
 * <p>
 */
public class SortList {

    public static void main(String[] args) {
        ListNode node = new ListNode(23);
        new SortList().sortList(node);
    }

    /**
     * 使用归并算法，类似数组的归并算法，n*log(n)
     *
     * @param head
     * @return
     */
    public ListNode sortList(ListNode head) {

        // 判断递归是否结束
        if (head == null || head.next == null) {
            return head;
        }

        // 找到子链表的中点节点
        ListNode midNode = middleNode(head);
        ListNode rightHead = midNode.next;
        midNode.next = null; // midNode作为前半段链表的尾结点


        // 讲中间节点前后的节点分别排序
        ListNode left = sortList(head);
        ListNode right = sortList(rightHead);

        // 合并两个有序的链表
        return mergeTwoLists(left, right);

    }

    // 找到链表中点节点
    ListNode middleNode(ListNode node) {
        if (node == null || node.next == null) {
            return node;
        }
        // slow移动一步，fast移动两步
        ListNode slow = node;
        ListNode fast = node.next;
        while (fast != null && fast.next != null) {
            // slow移动两步，fast移动一步
            slow = slow.next;
            fast = fast.next.next;
        }

        return slow;
    }

    // 合并两个有序的链表
    ListNode mergeTwoLists(ListNode leftNode, ListNode rightNode) {
        ListNode node = new ListNode(0);
        ListNode head = node;
        while (leftNode != null && rightNode != null) {
            if (leftNode.val < rightNode.val) {
                node.next = leftNode;
                leftNode = leftNode.next;
            } else {
                node.next = rightNode;
                rightNode = rightNode.next;
            }
            node = node.next;
        }

        // 不用再使用两个while循环添加链表节点了
        node.next = leftNode != null ? leftNode : rightNode;

        return head.next;
    }


    public static class ListNode {
        int val;
        ListNode next;

        ListNode(int x) {
            val = x;
        }
    }
}


